package solution1.demo.demo10;

<<<<<<< HEAD:demo/demo10/Solution.java
//import javafx.util.Pair;
//
//import java.util.*;
//
//  class TreeNode {
//      int val;
//      TreeNode left;
//      TreeNode right;
//      TreeNode() {}
//      TreeNode(int val) { this.val = val; }
//      TreeNode(int val, TreeNode left, TreeNode right) {
//          this.val = val;
//          this.left = left;
//          this.right = right;
//      }
//  }
//
//public class Solution {
//
//    //1.爬楼梯(完全背包)
//    public int climbStairs(int n) {
//        //从前 i 个爬法中任选，装满容量为 j 背包的方法
//        int[] dp = new int[n + 1];
//        dp[0] = 1;
//        for(int j = 0; j <= n; j++) {
//            for(int i = 1; i <= 2; i++) {
//                if(j >= i) {
//                    dp[j] = dp[j] + dp[j - i];
//                }
//            }
//        }
//        return dp[n];
//    }
//
//    //2.全排列II
//    private List<List<Integer>> res = new ArrayList<>();
//    private List<Integer> list = new ArrayList<>();
//    public List<List<Integer>> permuteUnique(int[] nums) {
//        boolean[] path = new boolean[nums.length];
//        permuteUniqueDfs(nums, path);
//        return res;
//    }
//
//    private void permuteUniqueDfs(int[] nums, boolean[] path) {
//        if(list.size() == nums.length) {
//            res.add(new ArrayList<>(list));
//            return;
//        }
//        Set<Integer> set = new HashSet<>();
//        for(int i = 0; i < nums.length; i++) {
//            if(path[i] || set.contains(nums[i])) {
//                continue;
//            }
//            set.add(nums[i]);
//            path[i] = true;
//            list.add(nums[i]);
//            permuteUniqueDfs(nums, path);
//            list.remove(list.size() - 1);
//            path[i] = false;
//        }
//    }
//
//    //3.零钱兑换(完全背包)
//    public int coinChange(int[] coins, int amount) {
//        //从前 i 个硬币中任选，装满容量为 j 的背包，最小硬币个数
//        int[] dp = new int[amount + 1];
//        Arrays.fill(dp, Integer.MAX_VALUE);
//        dp[0] = 0;
//        for(int i = 0; i < coins.length; i++) {
//            for(int j = coins[i]; j <= amount; j++) {
//                if(dp[j - coins[i]] != Integer.MAX_VALUE) {
//                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
//                }
//            }
//        }
//        if(dp[amount] == Integer.MAX_VALUE) {
//            return -1;
//        }
//        return dp[amount];
//    }
//
//    //4. 完全平方数(完全背包)
//    public int numSquares(int n) {
//        //从前 i 个商品中任选，装满容量为 j 的背包，需要的最少数量为 dp[j]
//        int[] dp = new int[n + 1];
//        Arrays.fill(dp, Integer.MAX_VALUE);
//        dp[0] = 0;
//        dp[1] = 1;
//        for(int i = 0; i <= Math.sqrt(n); i++) {
//            int val = i * i;
//            for(int j = val; j <= n; j++) {
//                if(dp[j - val] != Integer.MAX_VALUE) {
//                    dp[j] = Math.min(dp[j], dp[j - val] + 1);
//                }
//            }
//        }
//        return dp[n];
//    }
//
////    //5.单词拆分(完全背包)
////    public boolean wordBreak(String s, List<String> wordDict) {
////        boolean[] dp = new boolean[s.length() + 1];
////        dp[0] = true;
////        for(int i = 1; i <= s.length(); i++) {
////            for(int j = 0; j < i; j++) {
////                String str = s.substring(j, i);
////                if(wordDict.contains(str) && dp[j]) {
////                    dp[i] = true;
////                    break;
////                }
////            }
////        }
////        return dp[s.length()];
////    }
//
//    //6.单词拆分(完全背包)
=======

import java.util.*;

  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

public class Solution {

    //1.爬楼梯(完全背包)
    public int climbStairs(int n) {
        //从前 i 个爬法中任选，装满容量为 j 背包的方法
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for(int j = 0; j <= n; j++) {
            for(int i = 1; i <= 2; i++) {
                if(j >= i) {
                    dp[j] = dp[j] + dp[j - i];
                }
            }
        }
        return dp[n];
    }

    //2.全排列II
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> list = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] path = new boolean[nums.length];
        permuteUniqueDfs(nums, path);
        return res;
    }

    private void permuteUniqueDfs(int[] nums, boolean[] path) {
        if(list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            if(path[i] || set.contains(nums[i])) {
                continue;
            }
            set.add(nums[i]);
            path[i] = true;
            list.add(nums[i]);
            permuteUniqueDfs(nums, path);
            list.remove(list.size() - 1);
            path[i] = false;
        }
    }

    //3.零钱兑换(完全背包)
    public int coinChange(int[] coins, int amount) {
        //从前 i 个硬币中任选，装满容量为 j 的背包，最小硬币个数
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0; i < coins.length; i++) {
            for(int j = coins[i]; j <= amount; j++) {
                if(dp[j - coins[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if(dp[amount] == Integer.MAX_VALUE) {
            return -1;
        }
        return dp[amount];
    }

    //4. 完全平方数(完全背包)
    public int numSquares(int n) {
        //从前 i 个商品中任选，装满容量为 j 的背包，需要的最少数量为 dp[j]
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 0; i <= Math.sqrt(n); i++) {
            int val = i * i;
            for(int j = val; j <= n; j++) {
                if(dp[j - val] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - val] + 1);
                }
            }
        }
        return dp[n];
    }

//    //5.单词拆分(完全背包)
>>>>>>> ff3f488e325d7766c3bd91ad5d1691e123de9b38:solution1/demo/demo10/Solution.java
//    public boolean wordBreak(String s, List<String> wordDict) {
//        int len = s.length();
//        boolean[] dp = new boolean[len + 1];
//        dp[0] = true;
//        for(int i = 1; i <= len; i++) {
//            for(int j = 0; j < i; j++) {
//                String str = s.substring(j, i);
//                if(dp[j] && wordDict.contains(str)) {
//                    dp[i] = true;
//                    break;
//                }
//            }
//        }
//        return dp[len];
//    }
//
////    //7.打家劫舍(偷与不偷的问题)
////    public int rob(int[] nums) {
////        //从前 i 间房间中任选，最大价值是 dp[i];
////        //dp[i] = Math.max(偷当前这个房间 + dp[i - 2], 不偷这间房间，选择 dp[i - 1])
////        //dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
////        int len = nums.length;
////        int[] dp = new int[len + 1];
////        dp[1] = nums[0];
////        for(int i = 2; i <= len; i++) {
////            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
////        }
////        return dp[len];
////    }
//
//    //8.打家劫舍II(怎么偷的问题)
//    public int rob(int[] nums) {
//        if(nums.length == 1) {
//            return nums[0];
//        }
//        //偷第一家，不偷最后一家
//        int r1 = robFun(Arrays.copyOfRange(nums, 0, nums.length - 1));
//        //偷最后一家，不偷第一家
//        int r2 = robFun(Arrays.copyOfRange(nums, 1, nums.length));
//        return Math.max(r1, r2);
//    }
//
//    private int robFun(int[] nums) {
//        int len = nums.length;
//        int[] dp = new int[len + 1];
//        dp[1] = nums[0];
//        for(int i = 2; i <= len; i++) {
//            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
//        }
//        return dp[len];
//    }
<<<<<<< HEAD:demo/demo10/Solution.java
//
=======

    //8.打家劫舍II(怎么偷的问题)
    public int rob(int[] nums) {
        if(nums.length == 1) {
            return nums[0];
        }
        //偷第一家，不偷最后一家
        int r1 = robFun(Arrays.copyOfRange(nums, 0, nums.length - 1));
        //偷最后一家，不偷第一家
        int r2 = robFun(Arrays.copyOfRange(nums, 1, nums.length));
        return Math.max(r1, r2);
    }

    private int robFun(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len + 1];
        dp[1] = nums[0];
        for(int i = 2; i <= len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[len];
    }

>>>>>>> ff3f488e325d7766c3bd91ad5d1691e123de9b38:solution1/demo/demo10/Solution.java
//    //9.打家劫舍III (树形 dp)
//    public int rob(TreeNode root) {
//        Pair<Integer, Integer> pair = TreeDP(root);
//        return Math.max(pair.getKey(), pair.getValue());
//    }
//
//    private Pair<Integer, Integer> TreeDP(TreeNode root) {
//        if(root == null) {
//            return new Pair<>(0, 0);
//        }
//        Pair<Integer, Integer> left = TreeDP(root.left);
//        Pair<Integer, Integer> right = TreeDP(root.right);
//        //偷当前结点(不偷两个子节点)
//        int rob = left.getKey() + right.getKey() + root.val;
//        //不偷当前结点(两个子结点可以偷也可以不偷，就需要挑出最大的那个)
//        int notRob = Math.max(left.getKey(), left.getValue())
//                + Math.max(right.getKey(), right.getValue());
//        return new Pair<>(notRob, rob);
//    }
<<<<<<< HEAD:demo/demo10/Solution.java
//
//    //堆排序
//    public void heapSort(int[] arr) {
//        //创建一个大根堆
//        createBigHeap(arr);
//        for(int end = arr.length - 1; end > 0; end--) {
//            swap(arr, 0, end);
//            adjustDown(arr, 0, end);
//        }
//    }
//
//    private void createBigHeap(int[] arr) {
//        int len = arr.length;
//        for(int parent = (len - 1 - 1) / 2; parent >= 0; parent--) {
//            //对每一棵子树向下调整
//            adjustDown(arr, parent, len);
//        }
//    }
//
//    private void adjustDown(int[] arr, int parent, int len) {
//        int child = parent * 2 + 1;
//        while(child < len) {
//            if(child + 1 < len && arr[child] < arr[child + 1]) {
//                child++;
//            }
//            if(arr[child] > arr[parent]) {
//                swap(arr, child, parent);
//                parent = child;
//                child = child * 2 + 1;
//            } else {
//                break;
//            }
//        }
//    }
//
//    private void swap(int[] arr, int child, int parent) {
//        int tmp = arr[child];
//        arr[child] = arr[parent];
//        arr[parent] = tmp;
//    }
//
//    //10.分割等和子集(0-1背包)
//    public boolean canPartition(int[] nums) {
//        int sum = 0;
//        for(int i = 0; i < nums.length; i++) {
//            sum += nums[i];
//        }
//        if(sum % 2 == 1) {
//            return false;
//        }
//        int target = sum / 2;
//        int[] dp = new int[target + 1];
//        for(int i = 0; i < nums.length; i++) {
//            for(int j = target; j >= nums[i]; j--) {
//                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
//            }
//        }
//        return dp[target] == target;
//    }
//
//
//}
//
//class Main {
//    public static void main(String[] args) {
//        int[] arr = {1,5,11,5};
//        Solution solution = new Solution();
//        solution.canPartition(arr);
//    }
//}
//
=======

    //堆排序
    public void heapSort(int[] arr) {
        //创建一个大根堆
        createBigHeap(arr);
        for(int end = arr.length - 1; end > 0; end--) {
            swap(arr, 0, end);
            adjustDown(arr, 0, end);
        }
    }

    private void createBigHeap(int[] arr) {
        int len = arr.length;
        for(int parent = (len - 1 - 1) / 2; parent >= 0; parent--) {
            //对每一棵子树向下调整
            adjustDown(arr, parent, len);
        }
    }

    private void adjustDown(int[] arr, int parent, int len) {
        int child = parent * 2 + 1;
        while(child < len) {
            if(child + 1 < len && arr[child] < arr[child + 1]) {
                child++;
            }
            if(arr[child] > arr[parent]) {
                swap(arr, child, parent);
                parent = child;
                child = child * 2 + 1;
            } else {
                break;
            }
        }
    }

    private void swap(int[] arr, int child, int parent) {
        int tmp = arr[child];
        arr[child] = arr[parent];
        arr[parent] = tmp;
    }

    //10.分割等和子集(0-1背包)
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for(int i = 0; i < nums.length; i++) {
            for(int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }


}

class Main {
    public static void main(String[] args) {
        int[] arr = {1,5,11,5};
        Solution solution = new Solution();
        solution.canPartition(arr);
    }
}

>>>>>>> ff3f488e325d7766c3bd91ad5d1691e123de9b38:solution1/demo/demo10/Solution.java
